package com.yiwenup.sorting._01_bubble;

import com.yiwenup.sorting.base.Sort;

/**
 * 冒泡排序
 * 如果局部有序，则跳过
 * 时间复杂度：最好 - O(n)；最坏 - O(n²)；平均复杂度 - O(n²)
 * 空间复杂度：O(1)
 * 稳定性：稳定。相同元素之间的相对位置没有发生变化
 **/
public class BubbleSortV3<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void work() {
        for (int end = array.length - 1; end > 0; end--) {
            // idx = 1 在完全有序的时候，能够直接结束
            int idx = 1;
            for (int begin = 1; begin <= end; begin++) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    idx = begin;
                }
            }
            end = idx;
        }
    }
}
